import java.util.*;


public class BSTTest {

	public static void main( String[] args ) {
	
		final int SIZE = 1000;

		Random rand = new Random();
		Integer[] values = new Integer[SIZE];
		for (int i=0; i < SIZE; ++i) {
			values[ i ] = rand.nextInt();
		}

		BinarySearchTree bst = new BinarySearchTree();

		for (Integer val : values) {
			bst.insert( val );
		}

		Arrays.sort(values);

		for (Integer val : values) {
			test(bst.find(val) != null);
			test(bst.find(val) == val);
		}

		test(bst.findMin() == values[0]);
		test(bst.findMax() == values[values.length - 1]);

		int leftLow = 0;
		int leftHigh = SIZE / 2;
		int rightLow = leftHigh + 1;
		int rightHigh = SIZE - 1;

		while (leftLow <= leftHigh || rightLow <= rightHigh) {
		
			test(!bst.isEmpty());

			if (leftLow <= leftHigh) {
				test(bst.find( values[leftLow] ) == values[leftLow]);
				test(bst.findMin() == values[leftLow]);
				bst.remove(values[leftLow]);
				++leftLow;
			}
			
			if (leftLow <= leftHigh) {
				test(bst.find( values[leftHigh] ) == values[leftHigh]);
				bst.remove(values[leftHigh]);
				--leftHigh;
			}

			if (rightLow <= rightHigh) {
				test(bst.find( values[rightHigh] ) == values[rightHigh]);
				test(bst.findMax() == values[rightHigh]);
				bst.remove(values[rightHigh]);
				--rightHigh;
			}

			if (rightLow <= rightHigh) {
				test(bst.find( values[rightLow] ) == values[rightLow]);
				bst.remove(values[rightLow]);
				++rightLow;
			}
		}

		test(bst.isEmpty());

		System.out.println("All Tests Succeeded!");
	}

	private static void test(boolean condition) {
		if (!condition) {
			throw new IllegalStateException();
		}
	}

}